/*
 * @Author: liusheng
 * @Date: 2022-05-03 18:16:02
 * @LastEditors: liusheng
 * @LastEditTime: 2022-05-03 20:38:42
 * @Description: 剑指 Offer II 056. 二叉搜索树中两个节点之和
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 056. 二叉搜索树中两个节点之和
给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。

 

示例 1：

输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12
示例 2：

输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点
 

提示：

二叉树的节点个数的范围是  [1, 104].
-104 <= Node.val <= 104
root 为二叉搜索树
-105 <= k <= 105
 

注意：本题与主站 653 题相同： https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/

通过次数13,638提交次数18,574
 */
#include "header.h"
struct TreeNode {
    int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        if (root)
        {
            bool result = findTarget(root->left,k);
            if (result)
            {
                return true;
            }
            if (nums.count(k - root->val))
            {
                return true;
            }
            nums.insert(root->val);

            result = findTarget(root->right,k);
            
            if (result)
            {
                return true;
            }
        }

        return false;
    }
private:
    unordered_set<int> nums;
};

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        inorderTraverse(root);

        int n = nodeVals.size();
        int left = 0;
        int right = n - 1;
        while (left < right)
        {
            int sum = nodeVals[left] + nodeVals[right];
            if (k == sum)
            {
                return true;
            }
            
            if (sum > k)
            {
                --right;
            }
            else
            {
                ++left;
            }
        }
        return false;
    }
private:
    void inorderTraverse(TreeNode * root)
    {
        if (!root)
        {
            return;
        }

        inorderTraverse(root->left);
        nodeVals.push_back(root->val);
        inorderTraverse(root->right);
    }
private:
    vector<int> nodeVals;
};
